We consider a variant of the Cops and Robber game, introduced by Fomin,Golovach, Kratochvil, in which the robber has unbounded speed, i.e. can takeany path from her vertex in her turn, but she is not allowed to pass through avertex occupied by a cop. We study this game on interval graphs, chordalgraphs, planar graphs, and hypercube graphs. Let c_{\infty}(G) denote thenumber of cops needed to capture the robber in graph G in this variant. We showthat if G is an interval graph, then c_{\infty}(G) = O(sqrt(|V(G)|)), and wegive a polynomial-time 3-approximation algorithm for finding c_{\infty}(G) ininterval graphs. We prove that for every n there exists an n-vertex chordalgraph G with c_{\infty}(G) = Omega(n / \log n). Let tw(G) and Delta(G) denotethe treewidth and the maximum degree of G, respectively. We prove that forevery G, tw(G) + 1 \leq (Delta(G) + 1) c_{\infty}(G). Using this lower boundfor c_{\infty}(G), we show two things. The first is that if G is a planar graph(or more generally, if G does not have a fixed apex graph as a minor), thenc_{\infty}(G) = Theta(tw(G)). This immediately leads to an O(1)-approximationalgorithm for computing c_{\infty} for planar graphs. The second is that if Gis the m-hypercube graph, then there exist constants eta1, eta2>0 such that(eta1) 2^m / (m sqrt(m)) \leq c_{\infty}(G) \leq (eta2) 2^m / m.
展开▼
